package leetcode_100;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 *@author 周杨
 *WordSearch_79 在一个二维数组中搜索一个单词 要保证单词在数组中相邻出现并不重复提取 
 *describe: 用回溯法遍历 AC 17%
 *2018年5月14日 下午12:57:16
 */
public class WordSearch_79 {
	char [][] board;
	boolean [][]judge;
	String word;
	public static void main(String[] args) {
		WordSearch_79 test=new WordSearch_79();
		char [][] board=new char[][] {{'A','B','C','E'},{'S','F','C','S'},{'A','D','E','E'}};
		System.out.println(test.exist(board, "ABCCED"));
		System.out.println(test.exist(board, "SEE"));
		System.out.println(test.exist(board, "ABCB"));
		char[][] board1=new char[][] {{'a','a','a','a'},{'a','a','a','a'},{'a','a','a','a'}};
		System.out.println(test.exist(board1, "aaaaaaaaaaaaa"));
	}
	
	public boolean exist_(char[][] board, String word) {
		if(word.length()>board.length*board[0].length)
    		return false;
		char []chars=word.toCharArray();
		int row  = board.length;
		int col = board[0].length;
		boolean [][]visited=new boolean[row][col];
		Map<Character,List<Integer>> map= new HashMap<Character,List<Integer>>();
		for(int i=0;i<row;++i) {//构建字符map
			for(int j=0;j<col;++j) {
				List<Integer> list=map.getOrDefault(board[i][j], new ArrayList<Integer>());
				list.add(i);
				list.add(j);
				map.put(board[i][j],list);
			}
		}
		if(!map.containsKey(chars[0]))
			return false;//第一个就找不到
		List<Integer> start=map.get(chars[0]);
		for(int i=0;i<start.size();i+=2) {
			if(dfs(board, chars, 0, visited, start.get(i), start.get(i+1)))
				return true;
		}
		return false;
	}
	
	public boolean dfs(char[][]board,char []chars,int index,boolean [][]visited,int x,int y) {
		if(x<0||y<0||x==board.length||y==board[0].length||board[x][y]!=chars[index]||visited[x][y]) return false;
		if(index==chars.length-1) return true;
		boolean flag=false;
		visited[x][y]=true;
		flag=dfs(board,chars,index+1,visited,x+1,y)||dfs(board,chars,index+1,visited,x-1,y)
				||dfs(board,chars,index+1,visited,x,y+1)||dfs(board,chars,index+1,visited,x,y-1);
		visited[x][y]=false;
		return flag;
	}
	
    public boolean exist(char[][] board, String word) {
    	if(word.length()>board.length*board[0].length)
    		return false;
    	this.board=board;
    	this.word=word;
    	this.judge =new boolean[board.length][board[0].length];//用来判断哪些坐标是已经走过的
    	Map<Character,List<Integer>> map=new HashMap<Character,List<Integer>>();//用以记录哪个字母 出现在哪个位置
    	for(int i=0;i<board.length;++i)//构建字符地址map
    		for(int j=0;j<board[0].length;++j) {
    			List<Integer> list=map.get(board[i][j]);
    			if(list==null) {//第一次出现
    				list=new ArrayList<Integer>();
    				list.add(i);
    				list.add(j);
    				map.put(board[i][j], list);
    			}
    			else {
    				list.add(i);
    				list.add(j);
    			}
    		}
    	List<Integer> list=map.get(word.charAt(0));
    	if(list==null)
    		return false;
    	else {
    		boolean res=false;
    		for(int i=0;i<list.size();i+=2) {
    			res=help(list.get(i),list.get(i+1),0,0);//第一步已经校验
    			if(res)
    				return true;
    		}
    		return false;
    	}
    }
    
    public boolean help(int row,int col,int direction,int index) {//1 2 3 4 对应上下左右
    	if(row>=board.length||col>=board[0].length||col<0||row<0||index>=this.word.length())
    		return false;
    	if(this.word.charAt(index)!=board[row][col]) {//如果字符不匹配 直接返回false
    		return false;
    	}
    	else {//字符匹配
    		if(judge[row][col])
        		return false;
        	judge[row][col]=true;
    		if(index==this.word.length()-1){
    			return true;
    		}
    	}
    	boolean res=false;
    	if(direction!=2) {//上次走的下
    		res=help(row-1,col,1,index+1);
    	}
    	if(!res&&direction!=1)//上次走的上
    		res=help(row+1,col,2,index+1);
    	if(!res&&direction!=4)//上次走的右
    		res=help(row,col-1,3,index+1);
    	if(!res&&direction!=3)//上次走的左
    		res=help(row,col+1,4,index+1);
    	judge[row][col]=false;
    	return res;
    }

}
